package com.example.lettcode._202411._20241129;

import java.util.Arrays;

/*
643. 子数组最大平均数 I
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。

示例 1：
输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2：
输入：nums = [5], k = 1
输出：5.00000

提示：
n == nums.length
1 <= k <= n <= 105
-104 <= nums[i] <= 104
 */
public class _01_zi_shu_zu_zui_da_ping_jun_zhi {

    public static void main(String[] args) {
        int[] nums = {1,12,-5,-6,50,3};
        int k = 4;
        System.out.println(findMaxAverage4(nums, k));
    }

    public static double findMaxAverage(int[] nums, int k) {
        if (k == 0) {
            return 0;
        }
        double max = -Double.MAX_VALUE;
        for (int i = k-1; i < nums.length; i++) {
            double sum = 0;
            for (int j = i; j > i-k ; j--) {
                sum += nums[j];
            }
            max = Math.max(sum, max);
        }
        return max / (double) k;
    }


    /*
    上面那个超时了，先4个4个的求出综合
     */
    public static double findMaxAverage2(int[] nums, int k) {
        if (k == 0) {
            return 0;
        }
        int m = nums.length;
        int[] temp = new int[m-k+1];
        for (int i = 0; i < m-k+1; i++) {
            int sum = 0;
            for (int j = i; j < i + k; j++) {
                sum += nums[j];
            }
            temp[i] = sum;
        }
        Arrays.sort(temp);
        return (double) temp[temp.length - 1] / k;
    }


    /*
    上面那个还是超时了
    */
    public static double findMaxAverage3(int[] nums, int k) {
        if (k == 0) {
            return 0;
        }

        int sum = 0;
        int m = nums.length;
        int[] temp = new int[m-k+1];
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }

        temp[0] = sum;
        for (int i = 1; i < m-k+1; i++) {
            sum = sum - nums[i-1] + nums[i+k-1];
            temp[i] = sum;
        }
        Arrays.sort(temp);
        return (double) temp[temp.length - 1] / k;
    }


    public static double findMaxAverage4(int[] nums, int k) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }

        int maxRet = sum;
        for (int i = k; i < n; i++) {
            sum = sum - nums[i-k] + nums[i];
            maxRet = Math.max(maxRet, sum);
        }

        return 1.0 * maxRet / k;
    }
}
